﻿P1031[NOIP 2002 提高组] 均分纸牌
有 N 堆纸牌，编号分别为 1, 2, …, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N = 4 时，4 堆纸牌数分别为 9, 8, 17, 6。

移动 3 次可达到目的：

从第三堆取 4 张牌放到第四堆，此时每堆纸牌数分别为 9, 8, 13, 10。
从第三堆取 3 张牌放到第二堆，此时每堆纸牌数分别为 9, 11, 10, 10。
从第二堆取 1 张牌放到第一堆，此时每堆纸牌数分别为 10, 10, 10, 10。
输入格式
第一行共一个整数 N，表示纸牌堆数。
第二行共 N 个整数 A
1
​
, A
2
​
, …, A
N
​
，表示每堆纸牌初始时的纸牌数。

输出格式
共一行，即所有堆均达到相等时的最少移动次数。

输入输出样例
输入 #1复制

4
9 8 17 6
输出 #1复制

3
说明 / 提示
对于 100 % 的数据，1≤N≤100，1≤A
i
​
≤10000。

【题目来源】

NOIP 2002 提高组第一题



#include<bits/stdc++.h>
//思路： 我们可以知道总和一定是可以除n；那么最后每个位置都能变成average；因此可以从前往后遍历去调整即可！ 
//解法一：直接手动更改法：从前往后遍历，如果比average小此时就把负的差值移到后面去，如果比average大就把正的差值移到后面，
//依次类推，最后一次一定是等于aver（因为总和已经固定了，遍历的i前面的肯定已经变成aver） ，也就是我们满足i到达aver；把多出来的
//给后面，循环下去...

//解法二：也就是利用前缀和实现的解法一，不再修改原数组对应的下一个值，而是利用前缀和是否等于i*aver的比较来确定是否当前需要移动


//理解的关键就是 从前往后遍历，一个位置要变成aver，它会往后一个移动的这个差值就是正值或者负值，依次类推即可！ 
using namespace std;
int n;
int arr[1001];
int sum;
int cnt;
void greedy_solve1() {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    int aver = sum / n;//求出中位数 
    for (int i = 1; i <= n; i++) {
        if (arr[i] != aver) {
            arr[i + 1] += arr[i] - aver;//把需要转移的移到下一个位置上 
            cnt++;
        }

    }

    cout << cnt << endl;
}

void  greedy_solve2() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    int aver = sum / n;
    int dp;
    for (int i = 1; i <= n; i++) {
        dp += arr[i];//记录从一开始到达当前i位置的总和 
        if (dp != i * aver) cnt++;//如果等于则说明如果我们要是移动后，最后一次移动到i位置后，arr[i]此时满足aver！ 

    }

    cout << cnt << endl;

}
int main() {

    //greedy_solve1();
    greedy_solve2();
}